
/*-------------------------------------------------------------------------
 *
 * tsquery_cleanup.c
 *	 从 NOT 值和/或停用词中清理查询
 *	 修正工作的实用函数。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 *
 *
 * IDENTIFICATION
 *	  src/backend/utils/adt/tsquery_cleanup.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "miscadmin.h"
#include "tsearch/ts_utils.h"

typedef struct NODE
{
	struct NODE *left;
	struct NODE *right;
	QueryItem  *valnode;
} NODE;

/*
 * 从查询的简单视图构建查询树
 */
static NODE * fc_maketree(QueryItem *fc_in)
{
	NODE	   *fc_node = (NODE *) palloc(sizeof(NODE));

	/* 由于这个函数递归，它可能导致栈溢出。 */
	check_stack_depth();

	fc_node->valnode = fc_in;
	fc_node->right = fc_node->left = NULL;
	if (fc_in->type == QI_OPR)
	{
		fc_node->right = fc_maketree(fc_in + 1);
		if (fc_in->qoperator.oper != OP_NOT)
			fc_node->left = fc_maketree(fc_in + fc_in->qoperator.left);
	}
	return fc_node;
}

/*
 * plaintree 和 plainnode 的内部状态
 */
typedef struct
{
	QueryItem  *ptr;
	int			len;			/* ptr 的分配大小 */
	int			cur;			/* ptr 中的元素数量 */
} PLAINTREE;

static void fc_plainnode(PLAINTREE *fc_state, NODE *fc_node)
{
	/* 由于这个函数递归，它可能导致栈溢出。 */
	check_stack_depth();

	if (fc_state->cur == fc_state->len)
	{
		fc_state->len *= 2;
		fc_state->ptr = (QueryItem *) repalloc((void *) fc_state->ptr, fc_state->len * sizeof(QueryItem));
	}
	memcpy((void *) &(fc_state->ptr[fc_state->cur]), (void *) fc_node->valnode, sizeof(QueryItem));
	if (fc_node->valnode->type == QI_VAL)
		fc_state->cur++;
	else if (fc_node->valnode->qoperator.oper == OP_NOT)
	{
		fc_state->ptr[fc_state->cur].qoperator.left = 1;
		fc_state->cur++;
		fc_plainnode(fc_state, fc_node->right);
	}
	else
	{
		int			fc_cur = fc_state->cur;

		fc_state->cur++;
		fc_plainnode(fc_state, fc_node->right);
		fc_state->ptr[fc_cur].qoperator.left = fc_state->cur - fc_cur;
		fc_plainnode(fc_state, fc_node->left);
	}
	pfree(fc_node);
}

/* 从 NODE 树表示制作平面树视图 */
static QueryItem *
fc_plaintree(NODE *fc_root, int *fc_len)
{
	PLAINTREE	fc_pl;

	fc_pl.cur = 0;
	fc_pl.len = 16;
	if (fc_root && (fc_root->valnode->type == QI_VAL || fc_root->valnode->type == QI_OPR))
	{
		fc_pl.ptr = (QueryItem *) palloc(fc_pl.len * sizeof(QueryItem));
		fc_plainnode(&fc_pl, fc_root);
	}
	else
		fc_pl.ptr = NULL;
	*fc_len = fc_pl.cur;
	return fc_pl.ptr;
}

static void fc_freetree(NODE *fc_node)
{
	/* 由于这个函数递归，它可能导致栈溢出。 */
	check_stack_depth();

	if (!fc_node)
		return;
	if (fc_node->left)
		fc_freetree(fc_node->left);
	if (fc_node->right)
		fc_freetree(fc_node->right);
	pfree(fc_node);
}

/* 对于 ! 运算符清理树。 * * 这对于调试很有用，但在其他情况下，这种视图用于索引中的搜索。 * * 运算符 ! 始终返回 TRUE */
static NODE * fc_clean_NOT_intree(NODE *fc_node)
{
	/* 由于这个函数递归，它可能导致栈溢出。 */
	check_stack_depth();

	if (fc_node->valnode->type == QI_VAL)
		return fc_node;

	if (fc_node->valnode->qoperator.oper == OP_NOT)
	{
		fc_freetree(fc_node);
		return NULL;
	}

	/* 运算符 & 或 | */
	if (fc_node->valnode->qoperator.oper == OP_OR)
	{
		if ((fc_node->left = fc_clean_NOT_intree(fc_node->left)) == NULL ||
			(fc_node->right = fc_clean_NOT_intree(fc_node->right)) == NULL)
		{
			fc_freetree(fc_node);
			return NULL;
		}
	}
	else
	{
		NODE	   *fc_res = fc_node;

		Assert(fc_node->valnode->qoperator.oper == OP_AND ||
			   fc_node->valnode->qoperator.oper == OP_PHRASE);

		fc_node->left = fc_clean_NOT_intree(fc_node->left);
		fc_node->right = fc_clean_NOT_intree(fc_node->right);
		if (fc_node->left == NULL && fc_node->right == NULL)
		{
			pfree(fc_node);
			fc_res = NULL;
		}
		else if (fc_node->left == NULL)
		{
			fc_res = fc_node->right;
			pfree(fc_node);
		}
		else if (fc_node->right == NULL)
		{
			fc_res = fc_node->left;
			pfree(fc_node);
		}
		return fc_res;
	}
	return fc_node;
}

QueryItem *
clean_NOT(QueryItem *fc_ptr, int *fc_len)
{
	NODE	   *fc_root = fc_maketree(fc_ptr);

	return fc_plaintree(fc_clean_NOT_intree(fc_root), fc_len);
}


/* 从查询树中移除 QI_VALSTOP (停用词) 节点。 * * 如果查询退化为无，则返回 NULL。输入不能为空。 * * 当我们由于删除一个或两个参数而移除短语运算符时，可能需要调整父短语运算符的距离。 * 例如，'a' 是停用词，因此： * (b <-> a) <-> c 应变为 b <2> c * b <-> (a <-> c) 应变为 b <2> c * (b <-> (a <-> a)) <-> c 应变为 b <3> c * b <-> ((a <-> a) <-> c) 应变为 b <3> c * 为此，我们定义两个输出参数： * ladd: 要添加到此节点左侧短语距离的量 * radd: 要添加到此节点右侧短语距离的量 * 我们需要两个输出，因为可能需要将调整上浮到两个不同的父短语运算符。考虑 * w <-> (((a <-> x) <2> (y <3> a)) <-> z) * 在我们移除两个 a 并考虑 <2> 节点（现在仅为 x <2> y）时，我们有一个需要传播到最上层（最左边）<-> 的 ladd 距离 1，以及一个需要传播到最右边 <-> 的 radd 距离 3，因此我们最终将得到 * w <2> ((x <2> y) <4> z) * 在树的底部附近，我们可能会有仅包含停用词的子树。该子树中任何短语运算符的距离都将汇总并传播到 ladd 和 radd，因为我们不知道我们是在最低存活短语运算符的哪一侧。规则是，任何退化为 NULL 的子树必须返回相等的 ladd 和 radd 值，处理它的父节点应仅包含其中一个。 * 目前，我们仅对相邻短语运算符实现该调整。 * 例如，'x <-> ((a <-> y) | z)' 将变为 'x <-> (y | z)'，这并不理想，但没有办法表示真正期望的语义，而不对 tsquery 结构进行一些重设计。显然，将其转换为 'x <2> (y | z)' 也不会更好。由于这是一个非常奇怪的特例，暂时不予考虑。但是我们可以在中间非短语运算符也被移除的情况下修复它，例如 '((x <-> a) | a) <-> y' 将变为 'x <2> y'。 */
static NODE * fc_clean_stopword_intree(NODE *fc_node, int *fc_ladd, int *fc_radd)
{
	/* 由于这个函数递归，它可能导致栈溢出。 */
	check_stack_depth();

	/* 默认输出参数表示父距离没有变化 */
	*fc_ladd = *fc_radd = 0;

	if (fc_node->valnode->type == QI_VAL)
		return fc_node;
	else if (fc_node->valnode->type == QI_VALSTOP)
	{
		pfree(fc_node);
		return NULL;
	}

	Assert(fc_node->valnode->type == QI_OPR);

	if (fc_node->valnode->qoperator.oper == OP_NOT)
	{
		/* NOT 不会改变模式宽度，因此只需报告子距离 */
		fc_node->right = fc_clean_stopword_intree(fc_node->right, fc_ladd, fc_radd);
		if (!fc_node->right)
		{
			fc_freetree(fc_node);
			return NULL;
		}
	}
	else
	{
		NODE	   *fc_res = fc_node;
		bool		fc_isphrase;
		int			fc_ndistance,
					fc_lladd,
					fc_lradd,
					fc_rladd,
					fc_rradd;

		/* 首先，递归 */
		fc_node->left = fc_clean_stopword_intree(fc_node->left, &fc_lladd, &fc_lradd);
		fc_node->right = fc_clean_stopword_intree(fc_node->right, &fc_rladd, &fc_rradd);

		/* 检查当前节点是否为 OP_PHRASE，获取其距离 */
		fc_isphrase = (fc_node->valnode->qoperator.oper == OP_PHRASE);
		fc_ndistance = fc_isphrase ? fc_node->valnode->qoperator.distance : 0;

		if (fc_node->left == NULL && fc_node->right == NULL)
		{
			/* 当我们完全合并一个短语节点时，将其距离传播到 *ladd 和 *radd；父节点有责任仅计算一次。此外，对于短语节点，来自子节点的距离会被汇总并传播到父节点（我们假设 lladd == lradd 和 rladd == rradd，否则规则在下级中断）。但如果这不是一个短语节点，则取两个子距离中较大的一个；这对应于 TS_execute 在非停用词情况下的操作。 */
			if (fc_isphrase)
				*fc_ladd = *fc_radd = fc_lladd + fc_ndistance + fc_rladd;
			else
				*fc_ladd = *fc_radd = Max(fc_lladd, fc_rladd);
			fc_freetree(fc_node);
			return NULL;
		}
		else if (fc_node->left == NULL)
		{
			/* 移除此运算符和左子节点 */
			/* lladd 和 lradd 相等/冗余，不计入 */
			if (fc_isphrase)
			{
				/* 运算符自身的距离必须传播到左 */
				*fc_ladd = fc_lladd + fc_ndistance + fc_rladd;
				*fc_radd = fc_rradd;
			}
			else
			{
				/* 在非短语运算符处，完全忘记左子节点 */
				*fc_ladd = fc_rladd;
				*fc_radd = fc_rradd;
			}
			fc_res = fc_node->right;
			pfree(fc_node);
		}
		else if (fc_node->right == NULL)
		{
			/* 移除此运算符和右子节点 */
			/* rladd 和 rradd 相等/冗余，不计入 */
			if (fc_isphrase)
			{
				/* 运算符自身的距离必须传播到右 */
				*fc_ladd = fc_lladd;
				*fc_radd = fc_lradd + fc_ndistance + fc_rradd;
			}
			else
			{
				/* 在非短语运算符处，完全忘记右子节点 */
				*fc_ladd = fc_lladd;
				*fc_radd = fc_lradd;
			}
			fc_res = fc_node->left;
			pfree(fc_node);
		}
		else if (fc_isphrase)
		{
			/* 在此级别吸收适当的修正 */
			fc_node->valnode->qoperator.distance += fc_lradd + fc_rladd;
			/* 向上传播任何未计算的修正 */
			*fc_ladd = fc_lladd;
			*fc_radd = fc_rradd;
		}
		else
		{
			/* 我们保留了一个非短语运算符，因此 ladd/radd 仍为 0 */
		}

		return fc_res;
	}
	return fc_node;
}

/* 查询树中的元素数量 */
static int32 fc_calcstrlen(NODE *fc_node)
{
	int32		fc_size = 0;

	if (fc_node->valnode->type == QI_VAL)
	{
		fc_size = fc_node->valnode->qoperand.length + 1;
	}
	else
	{
		Assert(fc_node->valnode->type == QI_OPR);

		fc_size = fc_calcstrlen(fc_node->right);
		if (fc_node->valnode->qoperator.oper != OP_NOT)
			fc_size += fc_calcstrlen(fc_node->left);
	}

	return fc_size;
}

/* 从 TSQuery 中移除 QI_VALSTOP (停用词) 节点。 */
TSQuery cleanup_tsquery_stopwords(TSQuery fc_in)
{
	int32		fc_len,
				fc_lenstr,
				fc_commonlen,
				fc_i;
	NODE	   *fc_root;
	int			fc_ladd,
				fc_radd;
	TSQuery		fc_out;
	QueryItem  *fc_items;
	char	   *fc_operands;

	if (fc_in->size == 0)
		return fc_in;

	/* 消除停用词 */
	fc_root = fc_clean_stopword_intree(fc_maketree(GETQUERY(fc_in)), &fc_ladd, &fc_radd);
	if (fc_root == NULL)
	{
		ereport(NOTICE,
				(errmsg("text-search query contains only stop words or doesn't contain lexemes, ignored")));
		fc_out = palloc(HDRSIZETQ);
		fc_out->size = 0;
		SET_VARSIZE(fc_out, HDRSIZETQ);
		return fc_out;
	}

	/* 从平面视图构建 TSQuery */

	fc_lenstr = fc_calcstrlen(fc_root);
	fc_items = fc_plaintree(fc_root, &fc_len);
	fc_commonlen = COMPUTESIZE(fc_len, fc_lenstr);

	fc_out = palloc(fc_commonlen);
	SET_VARSIZE(fc_out, fc_commonlen);
	fc_out->size = fc_len;

	memcpy(GETQUERY(fc_out), fc_items, fc_len * sizeof(QueryItem));

	fc_items = GETQUERY(fc_out);
	fc_operands = GETOPERAND(fc_out);
	for (fc_i = 0; fc_i < fc_out->size; fc_i++)
	{
		QueryOperand *fc_op = (QueryOperand *) &fc_items[fc_i];

		if (fc_op->type != QI_VAL)
			continue;

		memcpy(fc_operands, GETOPERAND(fc_in) + fc_op->distance, fc_op->length);
		fc_operands[fc_op->length] = '\0';
		fc_op->distance = fc_operands - GETOPERAND(fc_out);
		fc_operands += fc_op->length + 1;
	}

	return fc_out;
}
